/LMAR=0/XLINE=3/FONT#0=BAXL30/FONT#1=BAXM30/FONT#2=BAXB30/FONT#3=SUB/FONT#4=SUP/FONT#5=BASL35/FONT#6=NGR25/FONT#7=MATH30/FONT#8=FIX25/FONT#9=GRK30



␈↓ ↓H␈↓α␈↓ αgPATTERN DIRECTED COMPUTATION AND PROBLEM SOLVING

␈↓ ↓H␈↓␈↓ α_This␈α∩is␈α∩a␈α∩preliminary␈α∩report␈α∩on␈α∪an␈α∩investigation␈α∩that␈α∩has␈α∩changed␈α∩its␈α∩character␈α∪as␈α∩it
␈↓ ↓H␈↓proceeded.␈α Since␈αI␈αam␈αnot␈αsure␈αwhere␈αit␈αwill␈αfinish,␈αI'll␈αstart␈αwith␈αthe␈αproblem␈αas␈αoriginally␈αposed
␈↓ ↓H␈↓and show how several stages of generalization have led to its present state.

␈↓ ↓H␈↓␈↓ α_We␈α∪begin␈α∪with␈α∪what␈α∪we␈α∪call␈α∪␈↓↓syntax-directed␈α∪computation␈↓␈α∪which␈α∪we␈α∪will␈α∪generalize␈α∩to
␈↓ ↓H␈↓␈↓↓pattern-directed␈αcomputation␈↓␈α
although␈αsyntactic␈αpatterns␈α
will␈αremain␈αan␈α
important␈αcase.␈α The␈α
term
␈↓ ↓H␈↓␈↓↓syntax-directed␈α⊂computation␈↓␈α⊂is␈α∂itself␈α⊂a␈α⊂generalization␈α∂of␈α⊂␈↓↓syntax-directed␈α⊂compiling␈↓␈α⊂and␈α∂␈↓↓syntax-
␈↓ ↓H␈↓↓directed input-output␈↓.

␈↓ ↓H␈↓␈↓ α_The␈αidea␈α
of␈αsyntax-directed␈α
computation␈αis␈α
quite␈αsimple␈α
and␈αquite␈α
old.␈α It␈α
is␈αquite␈α
tempting,
␈↓ ↓H␈↓for␈α∂example,␈α⊂to␈α∂try␈α∂to␈α⊂describe␈α∂differentiation␈α⊂and␈α∂algebraic␈α∂simplification␈α⊂with␈α∂a␈α⊂collection␈α∂of
␈↓ ↓H␈↓rules like

␈↓ ↓H␈↓␈↓ α_␈↓↓D(u + v) → Du + Dv␈↓

␈↓ ↓H␈↓and

␈↓ ↓H␈↓␈↓ α_␈↓↓u + 0 → u␈↓.

␈↓ ↓H␈↓We␈α
will␈α
work␈αin␈α
the␈α
framework␈αof␈α
LISP,␈α
for␈α
reasons␈αthat␈α
will␈α
become␈αapparent␈α
and␈α
which␈αare␈α
not
␈↓ ↓H␈↓merely parochial, so the above transformations become

␈↓ ↓H␈↓␈↓ α_(DIFF (PLUS U V)) → (PLUS (DIFF U) (DIFF V))

␈↓ ↓H␈↓and

␈↓ ↓H␈↓␈↓ α_(PLUS U 0) → U.

␈↓ ↓H␈↓At␈α
first␈α
sight␈α
it␈α
seems␈α
more␈α
pleasant␈α
to␈α
write␈αsuch␈α
rules␈α
than␈α
to␈α
write␈α
programs␈α
in␈α
LISP␈α
or␈αany
␈↓ ↓H␈↓other␈αprogramming␈αlanguage,␈αand␈αso␈αmany␈αspecial␈αlanguages␈αand␈αpackages␈αwithin␈αlanguages␈αlike
␈↓ ↓H␈↓LISP␈α∂have␈α∂been␈α∞written␈α∂that␈α∂interpret␈α∞collections␈α∂of␈α∂transformation␈α∞rules␈α∂or␈α∂compile␈α∂them␈α∞into
␈↓ ↓H␈↓program.

␈↓ ↓H␈↓␈↓ α_One␈α↔immediate␈α_question␈α↔is␈α↔whether␈α_there␈α↔is␈α↔any␈α_limit␈α↔on␈α↔what␈α_can␈α↔be␈α_done␈α↔by
␈↓ ↓H␈↓transformation␈α⊗rules␈α⊗or␈α⊗whether␈α⊗any␈α⊗computable␈α⊗function␈α⊗of␈α⊗symbolic␈α⊗expressions␈α⊗can␈α∃be
␈↓ ↓H␈↓computed␈α∩by␈α∩such␈α∩a␈α⊃system.␈α∩ The␈α∩answer␈α∩has␈α∩been␈α⊃known␈α∩since␈α∩the␈α∩1930s;␈α∩any␈α⊃computable
␈↓ ↓H␈↓function␈αcan␈αbe␈αcomputed␈αby␈αa␈αPost␈αcanonical␈αsystem␈αwhich␈αis␈αone␈αsystem␈αfor␈αwriting␈αsuch␈αrules.
␈↓ ↓H␈↓However,␈α∩the␈α⊃proof␈α∩involves␈α⊃using␈α∩such␈α∩rules␈α⊃to␈α∩simulate␈α⊃a␈α∩universal␈α⊃Turing␈α∩machine␈α∩or␈α⊃a
␈↓ ↓H␈↓computer␈α∞or␈α∞to␈α∞make␈α
a␈α∞set␈α∞of␈α∞rules␈α∞constituting␈α
an␈α∞interpreter␈α∞for␈α∞some␈α∞programming␈α
language.
␈↓ ↓H␈↓The␈α
state␈α
of␈α
the␈αcomputation␈α
is␈α
represented␈α
by␈α
a␈αsymbolic␈α
expression␈α
with␈α
special␈α
symbols␈αto␈α
mark
␈↓ ↓H␈↓the␈α
current␈α
instruction.␈α The␈α
syntax␈α
rules␈α
must␈αtherefore␈α
move␈α
the␈α
special␈αsymbol␈α
to␈α
search␈αfor␈α
the
␈↓ ↓H␈↓next instruction.

␈↓ ↓H␈↓␈↓ α_It␈αis␈αtherefore␈αentirely␈αclear␈αthat␈αthere␈αis␈αno␈αprogramming␈αor␈αpractical␈αadvantage␈αin␈αwriting
␈↓ ↓H␈↓syntax␈αtransformation␈αrules␈αto␈αsimulate␈αa␈αprogram.␈α Therefore,␈αthe␈αquestion␈αof␈αwhat␈α
computations
␈↓ ↓H␈↓are␈α∞conveniently␈α
done␈α∞by␈α∞sets␈α
of␈α∞syntax␈α
transformation␈α∞rules␈α∞remains.␈α
 The␈α∞practical␈α∞systems␈α
all
␈↓ ↓H␈↓allow␈α∂the␈α∂admixture␈α∂of␈α∂conventional␈α∂computation␈α∞in␈α∂one␈α∂way␈α∂or␈α∂another,␈α∂and␈α∂programmers␈α∞in
␈↓ ↓H␈↓these languages make frequent though often obscure use of these facilities.
␈↓ ↓H␈↓␈↓ εH␈↓ 91


␈↓ ↓H␈↓␈↓ α_These␈αpractical␈αlanguages␈αinclude␈αCOMIT␈α(early␈αbut␈αdefunct),␈αSNOBOL␈α(widely␈αused,␈αbut
␈↓ ↓H␈↓rarely␈α∩for␈α∩heavy␈α∩computation)␈α∩and␈α∩various␈α⊃packages␈α∩in␈α∩LISP␈α∩such␈α∩as␈α∩METEOR␈α∩(early␈α⊃but
␈↓ ↓H␈↓defunct) and also some of the features of Micro-planner and QLISP.

␈↓ ↓H␈↓␈↓ α_Our␈αfirst␈αidea␈αis␈αthat␈αinstantiation␈αis␈αa␈αspecial␈αcase␈αof␈αpattern␈αrecognition␈αwhich␈αis␈αa␈αspecial
␈↓ ↓H␈↓case␈α⊂of␈α∂problem␈α⊂solving.␈α⊂ We␈α∂start␈α⊂with␈α⊂the␈α∂LISP␈α⊂function␈α∂␈↓↓inst␈↓␈α⊂which␈α⊂does␈α∂a␈α⊂simple␈α⊂form␈α∂of
␈↓ ↓H␈↓instantiation␈αand␈α
generalize␈αit␈α
in␈αstages␈α
to␈αa␈αproblem␈α
solver␈αfor␈α
a␈αcertain␈α
class␈αof␈α␈↓↓obvious␈↓␈α
problems.
␈↓ ↓H␈↓In the present draft, it is not yet clear what our notion of ␈↓↓obvious␈↓ shall be.

␈↓ ↓H␈↓␈↓ α_We begin with

␈↓ ↓H␈↓␈↓ α_␈↓↓inst[pat,expr,a] ←
␈↓ ↓H␈↓␈↓ α_                ␈↓αif␈↓ a ␈↓αeq␈↓ NO␈↓↓ ␈↓αthen␈↓↓ ␈↓NO␈↓↓
␈↓ ↓H␈↓↓␈↓ α_                ␈↓αelse␈↓↓ ␈↓αif␈↓↓ isvar pat
␈↓ ↓H␈↓↓␈↓ α_                        ␈↓αthen␈↓↓ {assoc[pat,a]}[λz.
␈↓ ↓H␈↓↓␈↓ α_                                ␈↓αif␈↓↓ ␈↓αn␈↓↓ z ␈↓αthen␈↓↓ [pat.expr].a
␈↓ ↓H␈↓↓␈↓ α_                                ␈↓αelse␈↓↓ ␈↓αif␈↓↓ ␈↓αd␈↓↓ z ␈↓αeq␈↓↓ expr ␈↓αthen␈↓↓ a
␈↓ ↓H␈↓↓␈↓ α_                                ␈↓αelse␈↓↓ ␈↓NO␈↓↓]
␈↓ ↓H␈↓↓␈↓ α_                ␈↓αelse␈↓↓ ␈↓αif␈↓↓ ␈↓αat␈↓↓ pat ␈↓αthen␈↓↓ [␈↓αif␈↓↓ pat ␈↓αeq␈↓↓ expr ␈↓αthen␈↓↓ a ␈↓αelse␈↓↓ ␈↓NO␈↓↓]
␈↓ ↓H␈↓↓␈↓ α_                ␈↓αelse␈↓↓ ␈↓αif␈↓↓ ␈↓αat␈↓↓ expr ␈↓αthen␈↓↓ ␈↓NO␈↓↓
␈↓ ↓H␈↓↓␈↓ α_                ␈↓αelse␈↓↓ inst[␈↓αd␈↓↓ pat,␈↓αd␈↓↓ expr,inst[␈↓αa␈↓↓ pat,␈↓αa␈↓↓ expr,a]]]␈↓.

␈↓ ↓H␈↓␈↓ α_Here␈α
␈↓↓pat␈↓␈α
is␈αa␈α
pattern␈α
such␈αas␈α
(PLUS␈α
X␈α
Y)␈αwhere␈α
we␈α
suppose␈αthat␈α
the␈α
predicate␈α␈↓↓isvar␈↓␈α
knows
␈↓ ↓H␈↓that␈α
X␈α
and␈αY␈α
are␈α
variables␈αand␈α
PLUS␈α
is␈α
not.␈α ␈↓↓expr␈↓␈α
is␈α
an␈αexpression,␈α
for␈α
example␈α(PLUS␈α
(TIMES
␈↓ ↓H␈↓A␈α
B)␈α
C),␈αand␈α
␈↓↓a␈↓␈α
is␈α
an␈αa-list,␈α
i.e.␈α
a␈α
list␈αof␈α
dotted␈α
pairs,␈αeach␈α
of␈α
which␈α
is␈αa␈α
variable␈α
paired␈α
with␈αa
␈↓ ↓H␈↓value.  ␈↓↓inst␈↓ is usually called with ␈↓↓a = NIL␈↓, and we have

␈↓ ↓H␈↓␈↓ α_␈↓↓inst[␈↓(PLUS X Y),(PLUS (TIMES A B) C),NIL] = ((X . (TIMES A B))(Y . C)).

␈↓ ↓H␈↓In␈αgeneral,␈αhowever,␈α␈↓↓a␈↓␈αgives␈αthe␈αcommitments␈αfor␈αthe␈αvariables␈αthat␈αhave␈αalready␈αbeen␈αmade,␈α
and
␈↓ ↓H␈↓this␈αis␈α
used␈αin␈αthe␈α
recursion.␈α The␈α
value␈αof␈α␈↓↓inst[pat,expr,a]␈↓␈α
is␈αthe␈α
a-list␈αof␈αcommitments␈α
required
␈↓ ↓H␈↓to␈α∂make␈α∂the␈α∂pattern␈α∞␈↓↓pat␈↓␈α∂match␈α∂the␈α∂expression␈α∞␈↓↓expr.␈↓␈α∂ ␈↓↓inst␈↓␈α∂is␈α∂the␈α∞inverse␈α∂of␈α∂the␈α∂function␈α∞␈↓↓sublis␈↓
␈↓ ↓H␈↓defined by

␈↓ ↓H␈↓␈↓ α_␈↓↓sublis[a,pat]␈α∩←␈α∩                ␈↓αif␈↓↓␈α∩isvar␈α⊃pat␈α∩␈↓αthen␈↓↓␈α∩␈↓αd␈↓↓␈α∩assoc[pat,a]␈α∩                ␈↓αelse␈↓↓␈α⊃sublis[a,␈↓αa␈↓↓
␈↓ ↓H␈↓↓pat].sublis[a,␈↓αd␈↓↓ pat]␈↓.

␈↓ ↓H␈↓in the sense that

␈↓ ↓H␈↓␈↓ α_␈↓↓inst[pat,expr,a] ≠ ␈↓NO␈↓↓ ⊃ sublis[inst[pat,expr,a],pat] = expr␈↓.

␈↓ ↓H␈↓␈↓ α_When␈αwe␈αtry␈αto␈αuse␈α␈↓↓inst␈↓␈αfor␈αalgebraic␈αcomputation,␈αwe␈αimmediately␈αencounter␈αthe␈αfact␈αthat
␈↓ ↓H␈↓many␈αinteresting␈αoperations␈αsuch␈αas␈αaddition␈αare␈αcommutative,␈αand␈αour␈αpattern␈αrecognition␈αneeds
␈↓ ↓H␈↓to␈αtake␈α
this␈αinto␈α
account.␈α Thus␈α
if␈αwe␈α
want␈αa␈α
rule␈α␈↓↓cos␈↓∧2␈↓↓x + sin␈↓∧2␈↓↓x → 1␈↓,␈α
and␈αwe␈α
want␈αit␈α
to␈αrecognize
␈↓ ↓H␈↓␈↓↓cose␈↓∧2␈↓↓x␈↓␈αand␈α␈↓↓sin␈↓∧2␈↓↓x␈↓␈αanywhere␈αin␈αa␈αsum,␈αwe␈αcan't␈αdo␈α
it␈αwith␈α␈↓↓inst.␈↓␈α We␈αcan␈αpatch␈αup␈α␈↓↓inst␈↓␈αto␈αallow␈α
this
␈↓ ↓H␈↓by introducing the following term into its definition:

␈↓ ↓H␈↓Notes:
␈↓ ↓H␈↓␈↓ εH␈↓ 92


␈↓ ↓H␈↓␈↓ α_Bound␈αvariables␈αraise␈αtwo␈αkinds␈αof␈αproblem␈αfor␈αpattern␈αrecognition.␈α First,␈αa␈αfree␈αoccurence
␈↓ ↓H␈↓of␈αan␈αexpression␈αin␈αa␈αquantified␈αor␈αlambda-ized␈αcontext␈αshould␈αbe␈αtreated␈αcorrectly.␈α Second,␈αand
␈↓ ↓H␈↓ultimately␈α∞more␈α∞important,␈α∞λ-abstraction␈α
is␈α∞an␈α∞important␈α∞form␈α
of␈α∞pattern␈α∞recognition.␈α∞ Thus␈α
we
␈↓ ↓H␈↓would␈α
like␈α
to␈α
recognize␈α
␈↓↓(a + b)␈↓∧2␈↓↓ + a + b␈↓␈α
as␈α
an␈α
instance␈α
of␈α
␈↓↓f(a + b)␈↓.␈α
 It␈α
seems␈α
that␈α
recognition␈α
of␈α
such
␈↓ ↓H␈↓patterns␈α
is␈α
extremely␈α
powerful␈α
in␈α
that␈α
it␈α∞may␈α
contain␈α
a␈α
substantial␈α
part␈α
of␈α
the␈α
AI␈α∞problem␈α
and,
␈↓ ↓H␈↓consequently, extremely difficult.

␈↓ ↓H␈↓Higher␈α
order␈α
patterns:␈α
transitivity␈α
as␈α
a␈α
pattern␈αThe␈α
following␈α
pattern␈α
is␈α
satisfied␈α
by␈α
the␈αrelation␈α
of
␈↓ ↓H␈↓␈↓	x␈↓ of transitivity:

␈↓ ↓H␈↓␈↓ α_␈↓↓∀R.(␈↓	x␈↓↓(R) ∧ ∀xy.(Rxy ≡ Ryx) ⊃ ∃f.(Rxy ≡ f(x) = f(y)))␈↓.


␈↓ ↓H␈↓John McCarthy
␈↓ ↓H␈↓Artificial Intelligence Laboratory
␈↓ ↓H␈↓Computer Science Department
␈↓ ↓H␈↓Stanford University
␈↓ ↓H␈↓Stanford, California 94305

␈↓ ↓H␈↓ARPANET: MCCARTHY@SU-AI

␈↓ ↓H␈↓␈↓εThis draft of PATTER[F76,JMC] PUBbed at 11:30 on March 28, 1977.␈↓